/*
题目链接：https://leetcode.cn/problems/find-if-path-exists-in-graph/description/
	刘沛民	
*/

class Solution {
public:
    bool dfs(int source, int destination, vector<vector<int>>& adj, vector<bool> &visited)
    {
        if (source == destination)
        {
            return true;
        }
        visited[source] = true;

        for (int next : adj[source])
        {
            if (!visited[next] && dfs(next, destination, adj, visited))
                return true;
        }
        return false;
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n);
        for (auto &edge : edges)
        {
            int x = edge[0], y = edge[1];
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        vector<bool> visited(n, false);

        return dfs(source, destination, adj, visited);
    }
};